package cn.z2huo.algorithm.sort.swapSort.quickSort;

/**
 * 作者： 张一卓
 * 时间： 2020/1/14 19:13
 */
public class QuickSorting3 {
    public void sort(int[] array, int left, int right) {
        if (array == null) {
            return;
        }
        if (left >= right) {
            return;
        }
        int low = left, high = right;
        chooseMidValue(array, left, right);
//        int centerPosition = chooseMidValue(array, left, right);
        int centerPosition = left;
        int centerValue = array[centerPosition];
        while (low < high) {
            // 从序列末端寻找比 centerValue 小的元素
            while (array[high] >= centerValue && low < high) {
                high--;
            }
            // 从序列前端寻找比 centerValue 大的元素
            while (array[low] <= centerValue && low < high) {
                low++;
            }
            // 交换上面找到的两个元素的位置
            if (low < high) {
                int temp = array[high];
                array[high] = array[low];
                array[low] = temp;
            }
        }
        // 当low和high重合后，将 centerPosition 位置的元素值和 重合位置的元素值位置交换
        array[centerPosition] = array[low];
        array[low] = centerValue;

        centerPosition = low;

        sort(array, left, centerPosition - 1);
        sort(array, centerPosition + 1, right);
    }

    private int chooseMidValue(int[] array, int left, int right) {
        int mid = (left + right) / 2;
        if (left > mid) {
            swap(array, left, mid);
        }
        if (left > right) {
            swap(array, left, right);
        }
        if (mid > right) {
            swap(array, mid, right);
        }
        return mid;
    }

    private void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
